Many data compressors, such as those based on the LZ77 compression algorithm, perform data compression by replacing repeated data strings in an input data buffer with pointers to prior positions of the repeated strings in the input data buffer. Data compression is achievable because the pointers are typically smaller than the repeated data strings they replace. To find the repeated data strings in an input data buffer, some implementations of such data compressors utilize hash chain matching. In hash chain matching, a hash table is constructed with each entry corresponding to a respective data substring that was found previously in the input data buffer. Each entry of the hash table points to a respective hash chain storing the one or more positions in the input data buffer at which the particular data substring corresponding to the respective hash table entry was found. Data compressors can utilize such hash chains to limit the number of prior positions in the input data buffer to be searched when attempting to find a prior data string that matches and, thus, repeats a current data string beginning at the current position of the input data buffer undergoing compression.
The figures are not to scale. Wherever possible, the same reference numbers will be used throughout the drawing(s) and accompanying written description to refer to the same or like parts, elements, etc.